package org.example.myleet.p542;

public class Solution {
    /**
     * 思路：由于要求每个位置到0的最短距离，而这个距离是由旁边的位置决定的，因此整体上是动态规划
     * 但是需要从0的位置向周边延伸，因此需要BFS进行传播遍历
     */
    public int[][] updateMatrix(int[][] mat) {
        int[] dr = new int[]{-1, 0, 1, 0};
        int[] dc = new int[]{0, 1, 0, -1};
        int nr = mat.length, nc = mat[0].length, sr = 0, sc = 0;
        int[][] dp = new int[nr][nc];
        //初始化动态规划的状态，0的位置标0，周围标1，其余位置标无穷远
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (mat[i][j] == 0) {
                    sr = i;
                    sc = j;
                    dp[i][j] = 0;
                    for (int k = 0; k < 4; ++k) {
                        int r_ = i + dr[k];
                        int c_ = j + dc[k];
                        if (0 <= r_ && r_ < nr && 0 <= c_ && c_ < nc) {
                            dp[r_][c_] = Math.min(dp[r_][c_], 1);
                        }
                    }
                } else {
                    dp[i][j] = Integer.MAX_VALUE - 1;
                }
            }
        }
        //防止重复访问死循环
        boolean[][] visited = new boolean[nr][nc];
        //使用两个队列记录待遍历的位置
        int size = 0;
        int[][] pointQueue = new int[nr * nc][2];
        int[][] tempQueue = new int[nr * nc][2];
        //放入BFS起始点
        pointQueue[size++] = new int[]{sr, sc};
        visited[sr][sc] = true;
        while (size > 0) {
            int len = size;
            size = 0;
            for (int i = 0; i < len; ++i) {
                int[] p = pointQueue[i];
                //在该点4个方向进行更新和延伸
                for (int k = 0; k < 4; ++k) {
                    int r_ = p[0] + dr[k];
                    int c_ = p[1] + dc[k];
                    if (0 <= r_ && r_ < nr && 0 <= c_ && c_ < nc) {
                        dp[p[0]][p[1]] = Math.min(dp[p[0]][p[1]], dp[r_][c_] + 1);
                        dp[r_][c_] = Math.min(dp[p[0]][p[1]] + 1, dp[r_][c_]);
                        if (!visited[r_][c_]) {
                            tempQueue[size++] = new int[]{r_, c_};
                            visited[r_][c_] = true;
                        }
                    }
                }
            }
            if (size >= 0) System.arraycopy(tempQueue, 0, pointQueue, 0, size);
        }
        //最后再做一次修正
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                for (int k = 0; k < 4; ++k) {
                    int r_ = i + dr[k];
                    int c_ = j + dc[k];
                    if (0 <= r_ && r_ < nr && 0 <= c_ && c_ < nc) {
                        dp[i][j] = Math.min(dp[i][j], dp[r_][c_] + 1);
                    }
                }
            }
        }
        return dp;
    }
}
